package graph;

import java.util.*;

/**
 * Dijkstra（迪杰斯特拉算法）使用二叉堆优化的版本
 * 算法时间复杂度为 O(n^logn)
 * 支持获取源点到目标点的最短路径
 */
public class DijkstraGoodPath {
    /**
     * 获取源点到目标点的最短路路径
     *
     * @param source 源点
     * @param target 目标点
     */
    public static List<Edge<Integer>> dijkstra(Node<Integer> source, Node<Integer> target) {
        // 存储源点到任意节点的最短距离
        Map<Node<Integer>, Integer> distanceMap = new HashMap<>();
        // 记录距离自己最近的父节点
        Map<Node<Integer>, Node<Integer>> parentMap = new HashMap<>();

        NodeHeap<Integer> heap = new NodeHeap<>();
        heap.push(source, 0);
        while (!heap.isEmpty()) {
            // 每次弹出未确定最短距离且距离源点最近的点
            NodeHeap.NodeWithWeight<Integer> nodeWithWeight = heap.pop();
            // 对相邻的边进行松弛
            for (Edge<Integer> nextEdge : nodeWithWeight.getNode().nextEdges) {
                boolean updated = heap.push(nextEdge.to, nextEdge.weight + nodeWithWeight.getWeight());
                if (updated) {
                    // 记录源点到nextEdge.to节点的最短路径中，nextEdge.to节点的父节点
                    parentMap.put(nextEdge.to, nodeWithWeight.getNode());
                }
            }
            distanceMap.put(nodeWithWeight.getNode(), nodeWithWeight.getWeight());
            if (Objects.equals(nodeWithWeight.getNode(), target)) {
                // 找到了源点到目标点的最短路径
                break;
            }
        }

        if (!parentMap.containsKey(target)) {
            // 源点到目标点不可达
            return Collections.emptyList();
        }

        List<Edge<Integer>> result = new ArrayList<>();
        Node<Integer> node = target;
        Node<Integer> parent;
        // 回溯整条路径
        do {
            parent = parentMap.get(node);
            int distance = distanceMap.get(node) - distanceMap.get(parent);
            result.add(new Edge<>(distance, parent, node));
            node = parent;
        } while (source != parent);
        Collections.reverse(result);
        return result;
    }

}
